#include <stdio.h>
#include <stdlib.h>

/* https://c.biancheng.net/view/kruskal.html */
// 图中边的数量
#define N 9
// 图中顶点的数量
#define P 6

//构建表示边的结构体
typedef struct edge {
    //一条边有 2 个顶点
    int initial, end;
    //边的权值
    int weight;
}Edge;

//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序
int cmp(const void *a, const void *b) {
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

//克鲁斯卡尔算法寻找最小生成树，edges 存储用户输入的图的各个边，minTree 用于记录组成最小生成树的各个边
void kruskal_MinTree(Edge edges[], Edge minTree[]) {
    int initial, end, elem, j;
    //每个顶点配置一个标记值
    int assists[P];
    int num = 0;
    //初始状态下，每个顶点的标记都不相同
    for(int i = 0; i < P; i++) {
        assists[i] = i;
    }
    //根据权值，对所有边进行升序排序
    qsort(edges, N, sizeof(edges[0]), cmp);
    //遍历所有的边
    for(int i = 0; i < N; i++) {
        //找到当前边的两个顶点在 assists 数组中的位置下标
        initial = edges[i].initial - 1;
        end = edges[i].end - 1;
        //如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
        if(assists[initial] != assists[end]) {
            //记录该边，作为最小生成树的组成部分
            minTree[num] = edges[i];
            //计数+1
            num++;
            elem = assists[end];
            //将新加入生成树的顶点标记全部改为一样的
            for(j = 0; j < P; j++) {
                if(assists[j] == elem) {
                    assists[j] = assists[initial];
                }
            }
            //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
            if( num == P - 1) {
                break;
            }
        }
    }
}

void display(Edge minTree[]) {
    int cost = 0;
    printf("最小生成树为:\n");
    for(int i = 0; i < P - 1; i++) {
        printf("%d - %d 权值: %d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
        cost += minTree[i].weight;
    }
    printf("总权值为: %d", cost);
}

//构造无向网
void CreateUDN1(Edge array[]) {
    //在二维数组中添加弧的数据
    /*
    {
         A  B  C  D  S  T
    A    0  6  3  ∞  7  ∞
    B    6  0  4  2  ∞  5
    C    3  4  0  3  8  ∞
    D    ∞  2  3  0  ∞  2
    S    7  ∞  8  ∞  0  ∞
    T    ∞  5  ∞  2  ∞  0
    }
    */
   //无向图的二阶矩阵沿主对角线对称
   //A、B、C、D、S、T 顶点分别用数字 1~6 表示
   //A-B
   array[0].initial = 1;
   array[0].end = 2;
   array[0].weight = 6;
   //A-C
   array[1].initial = 1;
   array[1].end = 3;
   array[1].weight = 3;
   //B-C
   array[2].initial = 2;
   array[2].end = 3;
   array[2].weight = 4;
   //B-D
   array[3].initial = 2;
   array[3].end = 4;
   array[3].weight = 2;
   //B-T
   array[4].initial = 2;
   array[4].end = 6;
   array[4].weight = 5;
   //C-D
   array[5].initial = 3;
   array[5].end = 4;
   array[5].weight = 3;
   //C-S
   array[6].initial = 3;
   array[6].end = 5;
   array[6].weight = 8;
   //D-T
   array[7].initial = 4;
   array[7].end = 6;
   array[7].weight = 2;
   //S-A
   array[8].initial = 5;
   array[8].end = 1;
   array[8].weight = 7;
}

int main(int argc, char * argv[]) {
    Edge edges[N], minTree[P - 1];
    //调用创建函数，传入地址参数
    CreateUDN1(edges);
    printf("\n");
    kruskal_MinTree(edges, minTree);
    display(minTree);
    return 0;

}